package com.markpim.dena.opdracht4;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class GenericGraph {

	private Map<String, GraphVertex> vertices;

	public GenericGraph() {
		vertices = new HashMap<>();
	}

	// methods
	public void createInputCount() {
		// first reset inputCount
		for (Map.Entry<String, GraphVertex> entry : vertices.entrySet()) {
			entry.getValue().setInputCount(0);
		}

		// now calculate the inputCount again
		for (Map.Entry<String, GraphVertex> entry : vertices.entrySet()) {
			GraphVertex v = entry.getValue();
			for (GraphEdge e : v.getNeighboursOut()) {
				GraphVertex dest = e.getVertexTo();
				dest.setInputCount(dest.getInputCount() + 1);
			}
		}

		printInputCount();
	}
	
	public void createOutputCount() {
		for(GraphVertex vertex : vertices.values()) {
			vertex.setOutputCount(0);
		}
		
		for(GraphVertex vertex : vertices.values()) {
			for(GraphEdge e : vertex.getNeighboursIn()) {
				GraphVertex dest = e.getVertexFrom();
				dest.setOutputCount(dest.getOutputCount() + 1);
			}
		}
		
		printOutputCount();
	}

	private void printInputCount() {
		for (Map.Entry<String, GraphVertex> entry : vertices.entrySet()) {
			System.out.println("\t" + entry.getValue().getName() + " has inputCount: " + entry.getValue().getInputCount());
		}
	}
	
	private void printOutputCount() {
		for(GraphVertex v : vertices.values()) {
			System.out.println("\t" + v.getName() + " has outputCount: " + v.getOutputCount());
		}
	}

	// getters setters
	public void addVertex(String name) {
		vertices.put(name, new GraphVertex(name));
	}

	public void addEdge(String vertexFromName, String vertexToName, int weight) {
		GraphVertex vertexFrom = getVertex(vertexFromName);
		GraphVertex vertexTo = getVertex(vertexToName);
		if (vertexFrom != null) {
			GraphEdge edge = new GraphEdge(weight, getVertex(vertexFromName), getVertex(vertexToName));
			vertexFrom.addNeighbourOut(edge);
			vertexTo.addNeighbourIn(edge);
		}
	}

	private GraphVertex getVertex(String name) {
		return vertices.get(name);
	}
	
	private List<GraphVertex> getReversedTopologicalOrder() {
		List<GraphVertex> reversedTopologicalOrder = new ArrayList<>();
		Queue<GraphVertex> queue = new LinkedList<>();
		
		int count = 0;
		
		for(GraphVertex vertex : vertices.values()) {
			if(vertex.getOutputCount() == 0) {
				vertex.setLaatsteTijd(vertex.getVroegsteTijd());
				queue.add(vertex);
			}
		}
		
		while(!queue.isEmpty()) {
			GraphVertex vertex = queue.remove();
			count++;
			for(GraphEdge e : vertex.getNeighboursIn()) {
				GraphVertex neighbour = e.getVertexFrom();
				
				if(neighbour.decrementOutputCount() == 0) {
					queue.add(neighbour);
				}
			}
			reversedTopologicalOrder.add(vertex);
		}
		if (count != vertices.size())
			throw new IllegalStateException("Graph should not have cycles!");
		
		return reversedTopologicalOrder;
	}

	private List<GraphVertex> getTopologicalOrder() {
		List<GraphVertex> topologicalOrder = new ArrayList<>();
		Queue<GraphVertex> queue = new LinkedList<>();

		int count = 0;

		for (GraphVertex vertex : vertices.values()) {
			if (vertex.getInputCount() == 0)
				queue.add(vertex);
		}

		while (!queue.isEmpty()) {
			GraphVertex vertex = queue.remove();

			count++;

			for (GraphEdge edge : vertex.getNeighboursOut()) {
				GraphVertex neighbour = edge.getVertexTo();

				if (neighbour.decrementInputCount() == 0) {
					queue.add(neighbour);
				}
			}

			topologicalOrder.add(vertex);
		}

		if (count != vertices.size())
			throw new IllegalStateException("Graph should not have cycles!");

		return topologicalOrder;

	}

	public Map<String, Integer> vroegsteTijden() {
		for (GraphVertex vertex : getTopologicalOrder()) {
			int largest = 0;
			for (GraphEdge e : vertex.getNeighboursIn()) {
				if ((e.getVertexFrom().getVroegsteTijd() + e.getWeight()) > largest) {
					largest = (e.getVertexFrom().getVroegsteTijd() + e.getWeight());
				}
			}
			vertex.setVroegsteTijd(largest);
		}

		Map<String, Integer> output = new HashMap<>();

		for (GraphVertex vertex : vertices.values()) {
			output.put(vertex.getName(), vertex.getVroegsteTijd());
		}

		return output;
	}

	public Map<String, Integer> laatsteTijden() {
		List<GraphVertex> reversedTopologicalOrder = getReversedTopologicalOrder();
		for(GraphVertex vertex : reversedTopologicalOrder) {
			int smallest = -1;
			for(GraphEdge e : vertex.getNeighboursOut()) {
				if(smallest == -1 || (e.getVertexTo().getLaatsteTijd() - e.getWeight()) < smallest && e.getVertexTo().getLaatsteTijd() - e.getWeight() >= 0) {
					smallest = (e.getVertexTo().getLaatsteTijd() - e.getWeight());
				}
			}
			if(smallest != -1) {
				vertex.setLaatsteTijd(smallest);
			}
		}
		
		Map<String, Integer> output = new HashMap<>();
		
		for (GraphVertex vertex : vertices.values()) {
			output.put(vertex.getName(), vertex.getLaatsteTijd());
		}
		
		return output;
	}

}
